#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class loj_10147_solution_zkm{
public:
    loj_10147_solution_zkm(){
        int n;
        vector<int> arr;
        get_data(n, arr);
        // cout<<"get_data: "<<arr.size()<<endl;
        solve(n,arr);
    }
    void get_data(int &n ,vector<int> &arr){
        n = 4;
        arr = {4,5,9,4};
    }

    int help_min(int left, int right, vector<int>& arr, vector<int>& sums,vector<vector<int>>& dp1){
        if(left == right-1)return dp1[left][right] = arr[left]+arr[right];
        if(dp1[left][right]!=-1)return dp1[left][right];
        int cnts = arr[left]+sums[right]-sums[left];
        int ans = INT_MAX;
        for(int i=left+1;i<right-1;++i){
            ans = min(ans, help_min(left, i, arr, sums, dp1)+help_min(i+1, right,arr,sums, dp1));
        }
        return dp1[left][right]=ans+cnts;
    }

    int help_max(int left, int right, vector<int>& arr, vector<int>& sums,vector<vector<int>>& dp2){
        if(dp2[left][right]!=-1)return dp2[left][right];
        if(left == right-1)return dp2[left][right] = arr[left]+arr[right];
        int cnts = arr[left]+sums[right]-sums[left];
        int ans = INT_MIN;
        for(int i=left+1;i<right-1;++i){
            ans = max(ans, help_max(left, i, arr, sums,dp2)+help_max(i+1, right,arr, sums,dp2));
        }
        return dp2[left][right]=ans+cnts;
    }


    void solve(int n, vector<int>& arr){
        vector<vector<int>> dp1(n, vector<int>(n,-1)), dp2(n, vector<int>(n,-1));
        vector<int> sums(n);
        sums[0] = arr[0];
        for(int i = 1; i < n;++i) sums[i] = arr[i] + sums[i-1];

        cout<<help_min(0,n-1,arr, sums, dp1)<<endl;
        cout<<help_max(0,n-1, arr, sums, dp2)<<endl;
    }
};




